package leetcode.list;

/**
 * Created by zxc on 2018/10/3.
 * 链表划分，大于x的值放后面，小于x的值放前面，链表顺序不变
 */
public class PartitionList {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }

    /*链表划分，大于x的值放后面，小于x的值放前面，链表顺序不变*/
    private static ListNode partitionList(ListNode headA, int x) {
        ListNode tmpPreNode = new ListNode(0);
        ListNode tmpBehNode = new ListNode(0);
        ListNode tmpPreCopyNode = tmpPreNode;
        ListNode tmpBehCopyNode = tmpBehNode;

        while (headA != null) {
            if(headA.val < x){
                tmpPreCopyNode.next = headA;
                tmpPreCopyNode = headA;
            }else{
                tmpBehCopyNode.next = headA;
                tmpBehCopyNode = headA;
            }
            headA = headA.next;
        }
        // 将前半链表的尾与后半链表的头相连
        tmpPreCopyNode.next = tmpBehNode.next;
        tmpBehCopyNode.next = null;

        return tmpPreNode.next;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(2);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(2);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        node6.next=null;
        ListNode  headA = node1;

        System.out.println("Before 划分前:");
        System.out.print("headA:");
        int i=7;
        while (headA!=null){
            System.out.print(headA.val+">");
            headA = headA.next;
        }
        System.out.println("end");

        /*链表划分，大于等于x的值放后面，小于x的值放前面，链表顺序不变*/
        ListNode newHead = partitionList(node1, 3);

        if(newHead != null) {
            System.out.println("划分后：");
            while (newHead!=null){
                System.out.print(newHead.val+">");
                newHead = newHead.next;
            }

        }else{
            System.out.println("链表数据不对" );
        }

        System.out.println("end");
    }
}
